package com.zds.leetcode;

public class q_64 {
    public static void main(String[] args) {
        q_64 q = new q_64();
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(q.minPathSum2(grid));
    }

    /**
     * 常规使用 dp
     * @param grid
     * @return
     */
    public int minPathSum1(int[][] grid) {
        // 创建一个新的数组，存放该格子的最小和
        // i=0 和 j=0 的情况下最小和是固定的
        if (grid==null) {
            return 0;
        }
        // 另外数组处理技巧，如何取出二维数组的长度
        int row = grid.length, column = grid[0].length;
        int[][] dp = new int[row][column];
        // 初始位置赋值
        dp[0][0] = grid[0][0];
        for(int i = 1;i < row;i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int j = 1;j < column;j++){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        // 计算 dp 值
        for(int i = 1;i < row;i++){
            for(int j = 1;j < column;j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[row-1][column-1];
    }

    // 确实是可以使用原来的空间，直接覆盖
    public int minPathSum2(int[][] grid) {
        if (grid==null) {
            return 0;
        }
        int row = grid.length, column = grid[0].length;
        for(int i = 1;i < row;i++) {
            grid[i][0] = grid[i-1][0] + grid[i][0];
        }
        for(int j = 1;j < column;j++){
            grid[0][j] = grid[0][j-1] + grid[0][j];
        }
        // 计算 dp 值
        for(int i = 1;i < row;i++){
            for(int j = 1;j < column;j++) {
                grid[i][j] = Math.min(grid[i-1][j], grid[i][j-1]) + grid[i][j];
            }
        }
        return grid[row-1][column-1];
    }
}
